The present invention relates to multiprocessor computer systems and more particularly to an improved cross-connect circuit for connecting the various processors to memory modules which are shared by said processors.
One of the key components of a high performance multiprocessor system is the interconnection network between the processors and the memory. The bandwidth and latency of the interconnection network are two factors that influence the performance of the multiprocessor system. For example, doubling the data path width between the processor and the memory can potentially double the data available to a processor in a memory read. This can result in fewer memory references, fewer conflicts, and hence, increased performance. Reducing the latency in the interconnection network reduces the memory access time which can in turn improve the performance of the system.
Cross-connect systems have been in use in prior art computer systems for connecting the processors to the memory modules that make up the processor memory. In such systems, a processor wishing to execute an instruction that references a particular memory location requests a connection to the memory module containing the memory location in question. The cross-connect then connects the processor to the memory module, provided the memory module in question is not already connected to another processor. The frequency of such connection requests depends, in general, on the type of code being executed. For example, programs written in Pascal or C exhibit a local characteristic that minimizes the number of connection requests to be made. That is, the next instruction to be executed tends to reference memory locations close to those referenced by the last instruction. Hence, delays in performing the connection are acceptable, since the number of connections is small compared to the number of instructions executed.
Programs written in other languages such as Prolog do not share this locality trait. As a result, a processor's memory references may change from memory module to memory module in adjacent memory cycles. In such systems, delays due to low bandwidth in the cross-connect or long latency times after a connection request are unacceptable. Hence, prior art cross-connect have been found to be unsatisfactory for use in these systems.
For example, prior art chip designs that employ multi-stage cross-connect systems are known to the art (M. A. Franklin, D. F. Wann, and W. J. Thomas, "Pin Limitations and Partitioning of VLSI Interconnection Networks," IEEE Transactions on Computers Vol. C-31, No. 11, November 1982, and D. F. Wann and M. A. Franklin, J. Calvo, J. I. Acha, and M. Valencia, "Asynchronous Modular Arbiter," IEEE Transactions on Computers Volume C-35, No. 1, January 1986). However, the latency time of such systems is too long for such systems to be usable in computer systems which may require cross-connects to be made before every memory cycle.
Cross-connect chips with low latency times have been provided as a means of coupling the individual processors in a multiprocessor system to each other. For example, a 16.times.16 crossbar chip is utilized in the MARS system for connecting processors to each other (P. Agrawal, et al., "MARS: A Multiprocessor-based Programmable Accelerator," IEEE Design & Test of Computers Vol. 5, No. 4, pp 28-36, October 1987). Unfortunately, the arbiter used in the chip is based on positional priority. That is, when two processors request connection to the same memory module at the same time, one of the processors will always have priority over the other, since the processor priorities are assigned to each processor in advance based on the processor's address. In a cross-connect system for use in multiprocessor systems optimized for logic programs such as the Prolog programs mentioned above, all processors must have equal priority for optimum throughput. Hence, such cross-connect chips are unsatisfactory for use in such multiprocessor systems.
Broadly, it is an object of the present invention to provide an improved cross-connect chip for use in connecting the processors of a multiprocessor computer system to the memory modules thereof.
It is another object of the present invention to provide a cross-connect chip which has a low latency time.
It is yet another object of the present invention to provide a cross-connect chip which may be used to construct a cross-connect having an arbitrary bandwidth.
It is still another object of the present invention to provide a cross-connect chip having an arbiter which gives all processors equal priority in making any given cross-connect.
These and other objects of the present invention will become apparent to those skilled in the computer arts from the following detailed description of the invention and the accompanying drawings.